package mornd.binarysearch;

import org.junit.Test;

/**
 * @author: mornd
 * @dateTime: 2023/5/20 - 20:13
 * 普通二分查找
 */
public class Demo {
    @Test
    public void test() {
        int[] arr = {1, 2, 3};
        int target = 2;
        int r = binarySearch(target, arr);
        System.out.println(r);
    }

    private int binarySearch(int target, int[] arr) {
        int l, f, t;
        l = 0;
        f = arr.length - 1;
        while (l <= f) {
            // 无符号右移1位，效率高于/2,并且可以防止 int 存储溢出
            t = (l + f) >>> 1;
            System.out.println(t);
            if (arr[t] > target) {
                f = t - 1;
            } else if (arr[t] < target) {
                l = t + 1;
            } else {
                return t;
            }
        }
        // 未找到
        return -1;
    }

    @Test
    public void test2() {
        int l = 10;
        int r = Integer.MAX_VALUE;
        // 结果等价 = 1073741828
        int a = l / 2 + r / 2;
        int b = l + (r - l) / 2;
        int c = (l + r) >>> 1;

        int d = (l + r) / 2; // 结果溢出 -1073741819

        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
        System.out.println(d);
    }
}
